import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int findLongestChain(int[][] pairs) {
        // 预处理：对二维数组内的一维数组的首元素排序
        Arrays.sort(pairs, (a, b) -> a[0]-b[0]);

        // 创建dp表、初始化、填表、返回值
        int n = pairs.length;
        int[] dp = new int[n];

        Arrays.fill(dp, 1);

        for (int i = 1; i < n; i++) { // 为整个dp数组赋值
            for (int j = i-1; j >= 0; j--) { // 求单个dp值
                if (pairs[j][1] < pairs[i][0]) { // 满足题目要求
                    dp[i] = Math.max(dp[j]+1, dp[i]);
                }
            }
        }

        int ret = 0;
        for (int i = 0; i < n; i++) {
            ret = Math.max(dp[i], ret);
        }

        return ret;
    }
}

// 自己实现比较器
class cmp implements Comparator<int[]> {

    @Override
    public int compare(int[] o1, int[] o2) {
        // 比较首元素
        if (o1[0] == o2[0]) {
            return 0;
        }
        if (o1[0] > o2[0] ) {
            return 1;
        }
        return -1;
    }
}
